#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2

typedef struct ListNode
{
	int data;
	struct ListNode* next;
}listNode;

void PrintList(listNode* head)
{
	listNode* p = head;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}

listNode* CreateListNode(int data)
{
	listNode* newListNode = (listNode*)malloc(sizeof(listNode));
	if (!newListNode)return false;
	newListNode->data = data;
	newListNode->next = NULL;
	return newListNode;
}

void ConnectListNodes(listNode* node1, listNode* node2)
{
	node1->next = node2;
}

listNode* FindFirstCommonNode(listNode* pHead1, listNode* pHead2)
{
	listNode* p;
	listNode* shortList = pHead1;
	listNode* longList = pHead2;
	int length1 = 0;
	int length2 = 0;
	int lengthDif = 0;
	p = pHead1;
	while (p != NULL)
	{
		length1++;
		p = p->next;
	}
	p = pHead2;
	while (p != NULL)
	{
		length2++;
		p = p->next;
	}
	lengthDif = length2 - length1;
	if (lengthDif < 0)
	{
		shortList = pHead2;
		longList = pHead1;
		lengthDif = -lengthDif;
	}
	while (lengthDif != 0)
	{
		longList = longList->next;
		lengthDif--;
	}
	while (shortList != NULL && longList != NULL)
	{
		if (shortList == longList)break;
		shortList = shortList->next;
		longList = longList->next;
	}

	return shortList;

}
void main()
{
	int k = 1;
	listNode* pNode1 = CreateListNode(1);
	listNode* pNode2 = CreateListNode(2);
	listNode* pNode3 = CreateListNode(3);
	listNode* pNode4 = CreateListNode(4);
	listNode* pNode5 = CreateListNode(5);
	listNode* pNode6 = CreateListNode(6);
	listNode* pNode7 = CreateListNode(7);

	ConnectListNodes(pNode1, pNode2);
	ConnectListNodes(pNode2, pNode3);
	ConnectListNodes(pNode3, pNode6);
	ConnectListNodes(pNode6, pNode7);

	ConnectListNodes(pNode4, pNode5);
	ConnectListNodes(pNode5, pNode6);

	printf("%d", FindFirstCommonNode(pNode1, pNode4)->data);

}
